无等待排列流水车间提前/延期调度问题

doi:10.13190/jbupt.200906.72.140

北京邮电大学学报 ›› 2009, Vol. 32 ›› Issue (6): 72-76.doi: 10.13190/jbupt.200906.72.140

无等待排列流水车间提前/延期调度问题

宁维巍;雷毅;仲华惟;闫光荣

(北京航空航天大学机械工程及自动化学院, 北京 100191)

收稿日期:2009-03-28 修回日期:2009-05-10 出版日期:2009-12-28 发布日期:2009-12-28
通讯作者: 宁维巍

Researches on the No-Wait Permutation Flow Shop Earliness and Tardiness Scheduling Problem

NING Wei-wei;LEI Yi;ZHONG Hua-wei;YAN Guang-rong

(Department of Mechanical Engineering and Automation Specialized, Beihang University, Beijing 100191, China)

Received:2009-03-28 Revised:2009-05-10 Online:2009-12-28 Published:2009-12-28
Contact: NING Wei-Wei

摘要/Abstract

摘要：

在满足任务的交货期相同和工序无等待等假设条件后，提出了一种排列流水车间提前/延期惩罚调度问题的启发式算法. 该算法首先按照7种任务排序的规则分别得到任务的较优次序，然后分别使用NEH算法构造优化解，再对每个不同解进行邻域搜索，最后比较得出最优解. 在中小规模问题的数据实验中，该算法求解与最优解的相近程度达到99%左右，并且通过大量数据样本的标准差验证，求解的稳定性也非常好. 在大规模问题的数据实验中，该启发式算法体现出非常好的优化性能，同constraint programming(ILOG-CP）优化引擎算法比较，计算结果也明显占优.

关键词: 排列流水车间, 提前延期惩罚, 调度算法

Abstract:

Given the same due date and no idle time in processes, a heuristic algorithm for the earliness and tardiness penalties scheduling problem in permutation flow shop is proposed. Firstly, the algorithm gets the relatively good sequence of the jobs according to the sorted sequence regulation of 7 jobs. And then, the NEH algorithm is used to get the optimized solutions. At last, the optimal solutions are achieved by comparing the neighborhood searching results for every solutions. In the middle scale and small scale problems, the extent of similarity between the solutions got by the heuristic algorithm and the optimal solutions is 99%. Meanwhile through testing the standard deviation of the large scale samples, it is shown that the stability of the solutions is very good. In large scale problems, the heuristic algorithm appears good optimized performances and its calculated results are better than those got by ILOG-constraint programming(CP) optimized engine.

Key words: permutation flow shop, earliness and tardiness penalties, scheduling algorithm

宁维巍;雷毅;仲华惟;闫光荣. 无等待排列流水车间提前/延期调度问题[J]. 北京邮电大学学报, 2009, 32(6): 72-76.

NING Wei-wei;LEI Yi;ZHONG Hua-wei;YAN Guang-rong. Researches on the No-Wait Permutation Flow Shop Earliness and Tardiness Scheduling Problem[J]. JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM, 2009, 32(6): 72-76.

[1]	邹卫霞, 王海勇, 刘学锋. 基于区域用户密度的毫米波MU-MISO自适应调度方案[J]. 北京邮电大学学报, 2018, 41(2): 32-37.
[2]	朱春鸽, 张哲宇, 刘欣然, 孙斌, 张鸿. 虚拟计算环境下基于模糊聚类的资源调度算法[J]. 北京邮电大学学报, 2015, 38(s1): 6-9,19.
[3]	彭宏玉, 陈刚, 张英海, 王朝炜. SDN架构下数据中心内存能耗优化策略[J]. 北京邮电大学学报, 2015, 38(2): 78-82.
[4]	高雅, 邱智亮, 张健. 一种支持小扇出多播业务均衡的信元排队策略[J]. 北京邮电大学学报, 2014, 37(5): 91-95.
[5]	高雅, 邱智亮, 张茂森, 黎军. Clos交换网络中随机化的加权匹配调度算法[J]. 北京邮电大学学报, 2013, 36(4): 90-94.
[6]	黄胜李根庞洪丰李玲霞. POBS网络中异步突发延迟插空调度算法[J]. 北京邮电大学学报, 2013, 36(2): 70-73.
[7]	张翔李勇彭木根王文博江甲沫. TD-HSUPA MU-MIMO室内调度及用户配对[J]. 北京邮电大学学报, 2012, 35(2): 64-67.
[8]	李秀芹,兰巨龙,杨喜亮,程东年. 基于标识支持区分QoS的PPS调度机制[J]. 北京邮电大学学报, 2011, 34(4): 23-27.
[9]	王立磊;徐惠民. IEEE 802.16系统中针对AMR语音编码器的上行VoIP调度[J]. 北京邮电大学学报, 2009, 32(3): 100-103.
[10]	曹畅张永军李彬黄善国顾畹仪曹兴雯. T-MPLS网络中基于多等级业务的调度算法[J]. 北京邮电大学学报, 2009, 32(2): 119-122.
[11]	孙锴1，2，王莹1，2，王坦1，2，陈子雄1，2，张平1，2. 一种多用户MIMO/OFDMA系统的资源分配和调度方案[J]. 北京邮电大学学报, 2008, 31(5): 131-134.
[12]	孙锴1，2，王莹1，2，王坦1，2，陈子雄1，2，张平1，2. 一种多用户MIMO/OFDMA系统的资源分配和调度方案[J]. 北京邮电大学学报, 2008, 31(5): 131-134.
[13]	张学聃1, 洪珺1, 张林1, 李安国1,2，山秀明1. 并行图染色的无线网状网络媒体接入控制[J]. 北京邮电大学学报, 2007, 30(6): 36-39.
[14]	范晨，张琳，杨大成. 一种在混合业务中保证流业务QoS的调度算法[J]. 北京邮电大学学报, 2007, 30(3): 75-78.
[15]	隋延峰, 杨鸿文, 杨大成. 采用实时公平监测的改进最大C/I调度算法[J]. 北京邮电大学学报, 2007, 30(2): 132-135.

无等待排列流水车间提前/延期调度问题

Researches on the No-Wait Permutation Flow Shop Earliness and Tardiness Scheduling Problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价